#include <iostream>
#include <fstream>
#include <list>
#include <cstdlib>
#include "graph.h"
#include "queue/queue.h"
#include "edge.h"



using namespace std;

/*
 * Macierz sąsiedztwa
 *
 */

m_graph::m_graph(): adj_matrix(NULL){}

void m_graph::load(){
	int i, j;
	_V = 3;
	
  	adj_matrix = new int*[_V+1];

	for(i = 0 ; i <= _V; i++){
		adj_matrix[i] = new int[_V+1];
		for(j = 0 ; j <= _V; j++)
			adj_matrix[i][j] = 3;
	}
	
	adj_matrix[1][1] = 0;
	adj_matrix[1][2] = 0;
	adj_matrix[1][3] = 0;
    return;
}
void m_graph::load(const char* filename){	 

	
	fstream file;
	int  i, v1, v2, weight;

    file.open(filename, fstream::in);
    if(!file){
        cerr << "No file!" << endl;

        return;
    }
	file >> _V;
    file >> _E;	
	
	
	adj_matrix = new int*[_V+1];	

	for(int i = 0 ; i < _V+1; i++){
		adj_matrix[i] = new int[_V+1];
		for(int j =0 ; j < _V+1; j++)
			adj_matrix[i][j] = 0;
	}

	for(i = 0; i < _E; i++)
	{
        file >> v1;
        file >> v2;
        file >> weight;
        adj_matrix[v1][v2] = weight;

    }
	

}
int m_graph::V(){
	return _V;
}

int m_graph::E(){
	return _E;
}


m_graph::adj_ref m_graph::operator[](int n){

	return adj_iterator(&adj_matrix[n][1], &adj_matrix[n][1], _V);
}

m_graph_iter::m_graph_iter() : ptr(NULL){}

m_graph_iter::m_graph_iter(int* beg_ptr, int* ptr, int size) : beg_ptr(beg_ptr), ptr(ptr), size(size) {}

m_graph_iter m_graph_iter::begin() {

	while(*ptr == 0 && (ptr - beg_ptr) <= size )
		ptr++;
	
	return *this; 
}

m_graph_iter m_graph_iter::end() { 
	return m_graph_iter(this->beg_ptr, this->beg_ptr + this->size , this->size); 
}
 
std::pair<int, int> m_graph_iter::operator*(){ 
	return make_pair(ptr - beg_ptr+1, *ptr);
}

const m_graph_iter& m_graph_iter::operator++(){

	do{
		ptr++;
		//cout << this->end().ptr << endl;
	}while(*ptr == 0 && (ptr - beg_ptr) <= size ); 
		
	return *this;
}

bool m_graph_iter::operator!=(const m_graph_iter& other) const {
	return ptr != other.ptr;
}

/*
 * Lista sąsiędztwa
 *
 */

v_graph::v_graph(): adj_vector(NULL) {}
	
int v_graph::V(){
	return _V;
}

int v_graph::E(){
	return _E;
}

	
v_graph::adj_ref v_graph::operator[](int n){
	return *(adj_vector->begin() + n);
}

void v_graph::load(){

    adj_vector = new vector<map<int,int> >(3);
    
    _V = 2;
    (*adj_vector)[1][1] = 1;
    (*adj_vector)[1][2] = 2;
	(*adj_vector)[2][1] = 3;
	(*adj_vector)[2][2] = 4;
    return;
}


void v_graph::load(const char* filename){
    fstream file;
	int  i, v1, v2, weight;

    file.open(filename, fstream::in);
    if(!file){
        cerr << "No file!" << endl;
        return;
    }
	file >> _V;
    file >> _E;
	
    adj_vector = new vector<map<int,int> >(_V+1);

	for(i = 0; i < _E; i++){
        file >> v1;
        file >> v2;
        file >> weight;
        (*adj_vector)[v1][v2] = weight;
    }
    return;
}







/*
graph::graph(): V(0), E(0), adj_vector(NULL), adj_matrix(NULL){
}

int graph::getV(){
	return V;
}
int	graph::getE(){
	return E;
}

void graph::load_vector(const char* filename){
    fstream file;
	int  i, v1, v2, weight;

    file.open(filename, fstream::in);
    if(!file){
        cerr << "No file!" << endl;
        return;
    }
	file >> V;
    file >> E;
	
    adj_vector = new vector<map<int,int> >(V+1);

	for(i = 0; i < E; i++){
        file >> v1;
        file >> v2;
        file >> weight;
        (*adj_vector)[v1][v2] = weight;
    }
    return;
}

void graph::print_vector(){
	int i;
	map<int,int>::iterator j;

	cout << "V: " << V << endl 
		 << "E: " << E << endl << endl;

    for(i = 1; i <= V; i++ ){
        cout << i << ": ";
        for(j = (*adj_vector)[i].begin(); j != (*adj_vector)[i].end(); j++){
            cout << j->first << "(" << j->second <<") ";
        }
		cout << endl;
	}

    return;
}

void graph::load_list(const char* filename){
    fstream file;
	int  i, v1, v2, weight;

    file.open(filename, fstream::in);
    if(!file){
        cerr << "No file!" << endl;
        return;
    }
	file >> V;
    file >> E;
	
    adj_list = new list<map<int,int> >(V+1);

	for(i = 0; i < E; i++){
        file >> v1;
        file >> v2;
        file >> weight;

		list<map<int,int> >::iterator j = adj_list->begin();
		int counter = 1;
		while(counter < v1)
		{
			j++;
			counter++;
		}
		(*j)[v2] = weight;
		
		
    }
    return;
}

void graph::print_list()
{
	list<map<int,int> >::iterator i;
	map<int,int>::iterator j;

	int cntr1=1;
	for(i = adj_list->begin(); i != adj_list->end();i++)
	{
		cout<<cntr1<<": ";
		for(j = i->begin(); j != i->end(); j++)
		{
			cout<<j->first<<'('<<j->second<<") ";
		}
		cout<<'\n';
		cntr1++;
	}

}



void graph::load_matrix(const char* filename){	// adj_list sąsiedztwa   
	
	fstream file;
	int  i, v1, v2, weight;

    file.open(filename, fstream::in);
    if(!file){
        cerr << "No file!" << endl;
        return;
    }
	file >> V;
    file >> E;	
	
	
	adj_matrix = new int*[V+1];	//Tworzenie tablicy VxV
	for(int i = 0; i < V+1; i++)
		adj_matrix[i] = new int[V+1];

	for(int i = 0 ; i < V+1; i++)
		for(int j =0 ; j < V+1; j++)
			adj_matrix[i][j] = 0;

	for(i = 0; i < E; i++)
	{
        file >> v1;
        file >> v2;
        file >> weight;
        adj_matrix[v1][v2] = weight;
    }
	

}

void graph::print_matrix(){
	
	for(int i = 1 ; i < V; i++)
	{
		for(int j = 1 ; j < V; j++)
		{
			cout<<adj_matrix[i][j]<<' ';
		}
		cout<<endl;
	}
}



void graph::queue_tests(){
	queue *Q = new queue();
	int i, r, size;

	cout << "random: ";
	for(i = 0; i < 10; i++){
		r = rand() % 30;
		cout << r << " ";
		Q->insert(r);
	}
	cout << endl;

	cout << "values ";
	size = Q->size();
	for(int i = 0; i < size; i++){
		cout << Q->min_value() << " ";
		Q->extract_min();
    }
	cout << endl;

	cout << "random: ";
	for(i = 0; i < 10; i++){
		r = rand() % 30;
		cout << r << " ";
		Q->insert(r);
	}
	cout << endl;

	cout << "keys: ";
	size = Q->size();
	for(int i = 0; i < size; i++){
		cout << Q->min_key() << " ";
		Q->extract_min();
    }
	cout << endl;

	//delete Q;
	//Q = NULL;

	return;
}

int graph::bellman_ford(int start, int meta){
	int  *d, *pi, i, u, v, w;
	map<int,int>::iterator iter;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
	}
	d[start] = 0;

	for(i = 1 ; i < V; i++){

		for(u = 1; u <= V; u++){

			for(iter = (*adj_vector)[u].begin(); iter != (*adj_vector)[u].end(); iter++){
				v = iter->first;
				w = iter->second;
				if( d[v] > d[u] + w){
					d[v] = d[u] + w;
					pi[v] = u;
				}
			}
		}
	}

	meta = d[meta];
	delete [] d;
	delete [] pi;
	return  meta;
}


int graph::bellman_ford_matrix(int start, int meta){
	int  *d, *pi, i, u, v, w;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
	}
	d[start] = 0;

	for(i = 1 ; i < V; i++){

		for(u = 1; u <= V; u++){

			for(int j = 1; j <= V ; j++){
			
				if(adj_matrix[u][j] == 0)
					continue;
				v = j;
				w = adj_matrix[u][j];
				if( d[v] > d[u] + w){
					d[v] = d[u] + w;
					pi[v] = u;
				}	
			}
		}
	}


	meta = d[meta];
	delete [] d;
	delete [] pi;
	return  meta;
}


int graph::bellman_ford_list(int start, int meta){
	list<map<int,int> >::iterator iterator;
	map<int,int>::iterator k;

	int  *d, *pi, i, u, v, w;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
	}
	d[start] = 0;

	for(i = 1 ; i < V; i++){

		int cntr = 1;
		for(iterator = adj_list->begin(); iterator != adj_list->end(); iterator++)
		{
			u = cntr;
			for( k = iterator->begin(); k != iterator->end(); k++)
			{
				v = k->first;
				w = k->second;
				if( d[v] > d[u] + w)
				{
					d[v] = d[u] + w;
					pi[v] = u;
				}
			}
			cntr++;			
		}
		


		for(u = 1; u <= V; u++){

			for(int j = 1; j <= V ; j++)
		{
			if(adj_matrix[u][j] == 0)
				continue;
			v = j;
			w = adj_matrix[u][j];
			if( d[v] > d[u] + w){
				d[v] = d[u] + w;
				pi[v] = u;
			}
		}
		}
	}


	meta = d[meta];
	delete [] d;
	delete [] pi;
	return  meta;
}

int graph::dijkstra(int start, int meta){
    queue *Q = new queue(V);
	int *d, *pi, u, v, w, i;
    map<int,int>::iterator iter;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
		Q->insert(INF);
	}
	d[start] = 0;
    Q->decrease_value(start, 0);

    while(Q->size() != 1) {
		u = Q->min_key();
		Q->extract_min();

        for(iter = (*adj_vector)[u].begin(); iter != (*adj_vector)[u].end(); iter++ ){
			v = iter->first;
			w = iter->second;
			if( d[v] > d[u] + w){
				d[v] = d[u] + w;
				pi[v] = u;
				Q->decrease_value(v, d[v]);
			}
        }
    }

	meta = d[meta];
    delete [] d;
	delete [] pi;
	return  meta;
}


int graph::dijkstra_list(int start, int meta){
    queue *Q = new queue(V);
	int *d, *pi, u, v, w, i;
	list<map<int,int> >::iterator j;
    map<int,int>::iterator k;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
		Q->insert(INF);
	}
	d[start] = 0;
    Q->decrease_value(start, 0);

    while(Q->size() != 1) {
		u = Q->min_key();
		Q->extract_min();

		j = adj_list->begin();
		for(int cntr = 1; cntr < u ; cntr++)
			j++;

		for(k = j->begin(); k != j->end(); k++)
		{
			v = k->first;
			w = k->second;
			if( d[v] > d[u] + w){
				d[v] = d[u] + w;
				pi[v] = u;
				Q->decrease_value(v, d[v]);
			}
		}

    }

	meta = d[meta];
    delete [] d;
	delete [] pi;
	return  meta;
}


int graph::dijkstra_matrix(int start, int meta){
    queue *Q = new queue(V);
	int *d, *pi, u, v, w, i;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
		Q->insert(INF);
	}
	d[start] = 0;
    Q->decrease_value(start, 0);

    while(Q->size() != 1) {
		u = Q->min_key();
		Q->extract_min();

		for(int i = 1; i <= V ; i++)
		{
			if(adj_matrix[u][i] == 0)
				continue;
			v = i;
			w = adj_matrix[u][i];
			if( d[v] > d[u] + w){
				d[v] = d[u] + w;
				pi[v] = u;
				Q->decrease_value(v, d[v]);
			}
		}
    }

	meta = d[meta];
    delete [] d;
	delete [] pi;
	return  meta;
}


inline int find_set(int *pi, int x){
    if(pi[x] != x)
        pi[x] = find_set(pi, pi[x]);
    return pi[x];
}

inline void link(int *pi, int *rank, int x, int y){
	
	if(rank[x] > rank[y])
		pi[y] = x;
	else
		pi[x] = y;
    if(rank[x] == rank[y])
		rank[y]++;
}
	
inline bool edge_cmp(edge* e1, edge* e2){
	return e1->w < e2->w;
}
*/
/*
int graph::mst_kruskal(){
	int *pi, *rank, pi1, pi2, suma_mst, u;
	map<int,int>::iterator iter;
	list<edge*> edges;
	list<edge*>::iterator e;

	pi = new int [V+1];
    rank = new int[V+1];


    for(u = 1; u <= V; u++){
		for(iter = (*adj_vector)[u].begin(); iter != (*adj_vector)[u].end(); iter++){

			edges.push_back(new edge(u, iter->first, iter->second));
		}
		pi[u] = u;
		rank[u]=0;
    }

	edges.sort(edge_cmp);*/
/*
	for(e = edges.begin(); e != edges.end(); e++){
		cout << (**e).v1 << " "  <<  (**e).v2 << " " << (**e).w << endl;
	}
*//*
	suma_mst = 0;
    for(e = edges.begin(); e != edges.end(); e++){

        pi1 = find_set(pi, (**e).v1);
        pi2 = find_set(pi, (**e).v2);

        if(pi1 != pi2){ // różni ojcowie
            suma_mst += (**e).w;
			link(pi, rank, pi1, pi2);
        }
    }

	return suma_mst;
}*/
/*
int graph::mst_prim(int start){
	queue* Q = new queue();
	int suma_mst;
	list<edge*> MDR;
	list<edge*>::iterator e;
	map<int, int>::iterator it;
	
	map<int, bool> visited;				//All nodes are not visited

	for(int i=0;i<V;i++){
		Q->insert(INF);        // wrzucam same INF na kolejkę
		visited[i] = false;
	}
	int visited_count = 0;
	int weigh_sum = 0;

	int curr = start;
	suma_mst = 0;
	
	
	while(visited_count != V-1){

		visited[curr] = true;				//Current node visited
		visited_count++;

		for(it = (*adj_vector)[curr].begin();it != (*adj_vector)[curr].end(); it++){	

			if(!(visited[it->first]))
				Q->decrease_value(it->first, it->second); 
				// zamiast dodawać wierzchołek z wagą, obniżam wartość wagi zadanego wierzchołka z INF
		}
	
		
		suma_mst += Q->min_value();
		cout << suma_mst << " " << Q->min_key() << " " << Q->min_value() << endl;
		curr =  Q->min_key();
		Q->extract_min();
		//MDR.push_back(new edge(curr, prev, (*adj_vector)[curr][prev]));
	}


	//for(e = MDR.begin(); e != MDR.end(); e++){
	//	suma_mst += (**e).w;
	//	cout << (**e).v1 << " "  <<  (**e).v2 << " " << (**e).w << endl;
	//}
	delete Q;
	return suma_mst;
}*/
/*
int graph::mst_prim(int start){
	queue *Q = new queue(V);
	int *d, *pi, u, v, w, i, suma_mst;
    map<int,int>::iterator iter;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
		Q->insert(INF);
	}
	d[start] = 0;
    Q->decrease_value(start, 0);
	
	suma_mst = 0;

    while(Q->size() != 0) {
		u = Q->min_key();
		suma_mst += Q->min_value();
		Q->extract_min();

        for(iter = (*adj_vector)[u].begin(); iter != (*adj_vector)[u].end(); iter++ ){
			v = iter->first;
			w = iter->second;
			if( Q->in(v) && w < d[v] ){
				d[v] = w;
				pi[v] = u;
				Q->decrease_value(v, w);
			}
        }
    }

    delete [] d;
	delete [] pi;
	return suma_mst;
}

int graph::mst_prim_matrix(int start){
	queue *Q = new queue(V);
	int *d, *pi, u, v, w, i, suma_mst;
    map<int,int>::iterator iter;

	d = new int[V + 1];
	pi = new int[V + 1];

	for(i = 1; i <= V; i++){ 
		d[i] = INF;
		pi[i] = 0;
		Q->insert(INF);
	}
	d[start] = 0;
    Q->decrease_value(start, 0);
	
	suma_mst = 0;

    while(Q->size() != 0) {
		u = Q->min_key();
		suma_mst += Q->min_value();
		Q->extract_min();

		for(int i = 1; i <= V ; i++){

			if(adj_matrix[u][i] == 0)
				continue;
			v = i;
			w = adj_matrix[u][i];

			if( Q->in(v) && w < d[v] ){
				d[v] = w;
				pi[v] = u;
				Q->decrease_value(v, w);
			}
        }
    }

    delete [] d;
	delete [] pi;
	return suma_mst;
}*/
	/*
int graph::mst_kruskal_matrix(){
	int *pi, *rank, pi1, pi2, suma_mst, u, v, w;
	map<int,int>::iterator iter;
	list<edge*> edges;
	list<edge*>::iterator e;

	pi = new int [V+1];
    rank = new int[V+1];

	
    for(u = 1; u <= V; u++){
		for(int i = 1; i <= V ; i++){

			if(adj_matrix[u][i] == 0)
				continue;
			else{
				v = i;
				w = adj_matrix[u][i];
				edges.push_back(new edge(u, v, w));
			}
		}
		pi[u] = u;
		rank[u]=0;
    }

	edges.sort(edge_cmp);*/
/*
	for(e = edges.begin(); e != edges.end(); e++){
		cout << (**e).v1 << " "  <<  (**e).v2 << " " << (**e).w << endl;
	}
*//*
	suma_mst = 0;
    for(e = edges.begin(); e != edges.end(); e++){

        pi1 = find_set(pi, (**e).v1);
        pi2 = find_set(pi, (**e).v2);

        if(pi1 != pi2){ // różni ojcowie
            suma_mst += (**e).w;
			link(pi, rank, pi1, pi2);
        }
    }

	return suma_mst;
}
	
*/

